package com.xxd.algo.newcode.base01.class08;

/**
 * @author: XiaoDong.Xie
 * @create: 2021-01-18 15:18
 * @description:
 */
public class Knapsack {

    // 重量  3 2 4 7
    // 价值  5 6 3 19
    // 11
    public static int getMaxValue(int[] w, int[] v, int bag) {
        if (w == null || w.length == 0) {
            return 0;
        }
        if (v == null || v.length == 0) {
            return 0;
        }

        return process(w, v, 0, bag, 0);
    }

    private static int process(int[] w, int[] v, int index, int bag, int alreadyW) {
        if (alreadyW > bag) {
            return -1;
        }

        if (index == w.length) {
            return 0;
        }

        // 不要
        int p1 = process(w, v, index + 1, bag, alreadyW);

        // 要
        int p2 = process(w, v, index + 1, bag, alreadyW + w[index]);
        int p3 = 0;

        if (p2 != -1) {
            p3 = v[index] + p2;
        }

        return Math.max(p1, p3);
    }

    public static void main(String[] args) {
        int[] weights = {3, 2, 4, 7};
        int[] values = {5, 6, 3, 19};
        int bag = 11;
        System.out.println(getMaxValue(weights, values, bag));
    }
}
